#include "merge_sort.h"
#include <cstdlib>
#include <limits>

using namespace std;

void merge_sort(int* array, size_t p, size_t r)
{
    size_t q = ( p + r ) / 2;
    if ( q == p )
    {
        return;
    }

    merge_sort(array, p, q);
    merge_sort(array, q, r);

    merge(array, p, q, r);
}

void merge(int* array, size_t p, size_t q, size_t r)
{
    /* do not use sentinels */
    int* left = (int*)malloc(sizeof(int) * ( q - p ));
    for ( size_t i = p; i < q; ++i )
    {
        left[i - p] = array[i];
    }

    
    int* right = (int*)malloc(sizeof(int) * ( r - q ));
    for ( size_t i = q; i < r; ++i )
    {
        right[i - q] = array[i];
    }

    size_t j = 0;
    size_t k = 0;
    size_t i = p;

    for (; i < r; ++i )
    {
        if ( (j >= q - p) || (k >= r - q) )
        {
            break;
        }

        if ( left[j] < right[k] )
        {
            array[i] = left[j];
            ++j;
        }
        else
        {
            array[i] = right[k];
            ++k;
        }
    }

    while ( j < q - p )
    {
        array[i++] = left[j++];
    }

    while ( k < r - q )
    {
        array[i++] = right[k++];
    }

    free(left);
    free(right);
}

